package leetcode_周赛._2021._202105._20210509;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/9 11:58
 * 子数组最小乘积的最大值
 * 找到子数组
 * 去掉的值最小，而留下的和要尽可能的大
 * sum，del
 * min * （sum - del）
 * 怎么删除元素中的值，使得到的数组的最小乘积最大
 * 子数组为原数组的连续部分
 * 不是考虑要删除哪个数，而是要留下哪些数
 */
public class _5752 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 2};
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        Arrays.fill(right, n - 1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                right[stack.peek()] = i - 1;
                stack.pop();
            }
            if (!stack.isEmpty()) left[i] = stack.peek() + 1;
            stack.push(i);
        }
        System.out.println(Arrays.toString(left));
        System.out.println(Arrays.toString(right));
        System.out.println(stack);
    }

    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n];
        Arrays.fill(right, n - 1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                right[stack.peek()] = i - 1;
                stack.pop();
            }
            if (!stack.isEmpty()) left[i] = stack.peek() + 1;
            stack.push(i);
        }
        return 0;
    }
}
